package me.eg.second;

import java.util.HashMap;
import java.util.Map;

/**
 * 560. 和为 K 的子数组
 *
 * https://leetcode-cn.com/problems/subarray-sum-equals-k/
 */
public class SubarraySum {
    public int subarraySum(int[] nums, int k) {
        // 先计算前缀和
        // 目标：sum[l..r] = k => sum[r] - sum[l - 1] = k
        // r固定：找l，使得 sum[l - 1] = sum[r] - k;
        int len = nums.length;
        int[] sums = new int[len + 1];
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        int ans = 0;
        for (int i = 1; i <= len; i++) {
            sums[i] = sums[i - 1] + nums[i - 1];
            // 注意：这里先找目标结果，再往map添加
            // 因为要保证 l 比 r 小
            ans += map.getOrDefault(sums[i] - k, 0);
            map.put(sums[i], map.getOrDefault(sums[i], 0) + 1);
        }
        return ans;
    }
}
